package leetCode;

import com.google.common.base.Stopwatch;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;
import java.util.concurrent.TimeUnit;

/**
 * Created by liyong on 16/5/14.
 */
public class UglyNumberMinHeap {

  public int nthUglyNumber(int n) {
    if (1 == n) {
      return 1;
    }
    MinHeap treeSetTwo = new MinHeap();
    MinHeap treeSetThree = new MinHeap();
    MinHeap treeSetFive = new MinHeap();
    treeSetTwo.insert(1);
    treeSetThree.insert(1);
    treeSetFive.insert(1);
    int lastResult = 1;
    for (int index = 2; index <= n; index++) {
      int minTwo = treeSetTwo.first();
      int minThree = treeSetThree.first();
      int minFive = treeSetFive.first();
      int candidateTwo = minTwo * 2;
      int candidateThree = minThree * 3;
      int candidateFive = minFive * 5;
      int result = lastResult;

      if (candidateTwo < candidateThree && candidateTwo < candidateFive) {
        result = candidateTwo;
        treeSetTwo.remove();
      } else if (candidateThree < candidateTwo && candidateThree < candidateFive){
        result = candidateThree;
        treeSetThree.remove();
      } else if (candidateFive < candidateTwo && candidateFive < candidateThree) {
        result = candidateFive;
        treeSetFive.remove();
      } else if (candidateTwo == candidateThree && candidateTwo < candidateFive) {
        result = candidateTwo;
        treeSetTwo.remove();
        treeSetThree.remove();
      } else if (candidateTwo == candidateFive && candidateTwo < candidateThree) {
        result = candidateTwo;
        treeSetTwo.remove();
        treeSetFive.remove();
      } else if (candidateFive == candidateThree && candidateFive < candidateTwo) {
        result = candidateFive;
        treeSetThree.remove();
        treeSetFive.remove();
      } else if (candidateFive == candidateThree && candidateFive == candidateTwo) {
        result = candidateFive;
        treeSetFive.remove();
        treeSetThree.remove();
        treeSetTwo.remove();
      }
      if (lastResult < result ) {
        treeSetTwo.insert(result);
        treeSetThree.insert(result);
        treeSetFive.insert(result);
        lastResult = result;
      } else {
        index--;
      }
    }
    return lastResult;
  }
  
  private int getFirst(TreeSet<Integer> treeSet) {
    if(null == treeSet || treeSet.isEmpty()) {
      return Integer.MAX_VALUE;
    } else {
      return treeSet.first();
    }
  }

  public class MinHeap {

    private List<HuffmanNode> mHeap;		// 存放堆的数组

    /*
     * 创建最小堆
     *
     * 参数说明：
     *     a -- 数据所在的数组
     */
    protected MinHeap(int a[]) {
      mHeap = new ArrayList<HuffmanNode>();
      // 初始化数组
      for(int i=0; i<a.length; i++) {
        HuffmanNode node = new HuffmanNode(a[i], null, null, null);
        mHeap.add(node);
      }

      // 从(size/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个最小堆。
      for (int i = a.length / 2 - 1; i >= 0; i--)
        filterdown(i, a.length-1);
    }

    protected MinHeap() {
      mHeap = new ArrayList<HuffmanNode>();
    }

    /*
     * 最小堆的向下调整算法
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
     *     end   -- 截至范围(一般为数组中最后一个元素的索引)
     */
    protected void filterdown(int start, int end) {
      int c = start; 	 	// 当前(current)节点的位置
      int l = 2*c + 1; 	// 左(left)孩子的位置
      HuffmanNode tmp = mHeap.get(c);	// 当前(current)节点

      while(l <= end) {
        // "l"是左孩子，"l+1"是右孩子
        if(l < end && (mHeap.get(l).compareTo(mHeap.get(l+1))>0))
          l++;		// 左右两孩子中选择较小者，即mHeap[l+1]

        int cmp = tmp.compareTo(mHeap.get(l));
        if(cmp <= 0)
          break;		//调整结束
        else {
          mHeap.set(c, mHeap.get(l));
          c = l;
          l = 2*l + 1;
        }
      }
      mHeap.set(c, tmp);
    }

    /*
     * 最小堆的向上调整算法(从start开始向上直到0，调整堆)
     *
     * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
     *
     * 参数说明：
     *     start -- 被上调节点的起始位置(一般为数组中最后一个元素的索引)
     */
    protected void filterup(int start) {
      int c = start;			// 当前节点(current)的位置
      int p = (c-1)/2;		// 父(parent)结点的位置
      HuffmanNode tmp = mHeap.get(c);	// 当前(current)节点

      while(c > 0) {
        int cmp = mHeap.get(p).compareTo(tmp);
        if(cmp <= 0)
          break;
        else {
          mHeap.set(c, mHeap.get(p));
          c = p;
          p = (p-1)/2;
        }
      }
      mHeap.set(c, tmp);
    }

    /*
     * 将node插入到二叉堆中
     */
    protected void insert(HuffmanNode node) {
      int size = mHeap.size();

      mHeap.add(node);	// 将"数组"插在表尾
      filterup(size);		// 向上调整堆
    }

    protected void insert(int n) {
      HuffmanNode node = new HuffmanNode(n, null, null, null);
      insert(node);
    }

    /*
     * 交换两个HuffmanNode节点的全部数据
     */
    private void swapNode(int i, int j) {
      HuffmanNode tmp = mHeap.get(i);
      mHeap.set(i, mHeap.get(j));
      mHeap.set(j, tmp);
    }

    /*
     * 新建一个节点，并将最小堆中最小节点的数据复制给该节点。
     * 然后除最小节点之外的数据重新构造成最小堆。
     *
     * 返回值：
     *     失败返回null。
     */
    protected HuffmanNode dumpFromMinimum() {
      int size = mHeap.size();

      // 如果"堆"已空，则返回
      if(size == 0)
        return null;

      // 将"最小节点"克隆一份，将克隆得到的对象赋值给node
      HuffmanNode node = (HuffmanNode)mHeap.get(0).clone();

      // 交换"最小节点"和"最后一个节点"
      mHeap.set(0, mHeap.get(size-1));
      // 删除最后的元素
      mHeap.remove(size-1);

      if (mHeap.size() > 1)
        filterdown(0, mHeap.size()-1);

      return node;
    }

    public int remove() {
      HuffmanNode node = dumpFromMinimum();
      return node.key;
    }

    public int first() {
      if (mHeap.isEmpty()) {
        return Integer.MAX_VALUE;
      }
      return mHeap.get(0).key;
    }

    // 销毁最小堆
    protected void destroy() {
      mHeap.clear();
      mHeap = null;
    }
  }

  public class HuffmanNode implements Comparable, Cloneable {
    protected int key;				// 权值
    protected HuffmanNode left;		// 左孩子
    protected HuffmanNode right;	// 右孩子
    protected HuffmanNode parent;	// 父结点

    protected HuffmanNode(int key, HuffmanNode left, HuffmanNode right, HuffmanNode parent) {
      this.key = key;
      this.left = left;
      this.right = right;
      this.parent = parent;
    }

    @Override
    public Object clone() {
      Object obj=null;

      try {
        obj = (HuffmanNode)super.clone();//Object 中的clone()识别出你要复制的是哪一个对象。
      } catch(CloneNotSupportedException e) {
        System.out.println(e.toString());
      }

      return obj;
    }

    @Override
    public int compareTo(Object obj) {
      return this.key - ((HuffmanNode)obj).key;
    }
  }

  public static void main(String[] arg) {
    Stopwatch wholeStopWatch = Stopwatch.createStarted();
    UglyNumberMinHeap uglyNumber = new UglyNumberMinHeap();
    System.out.println(uglyNumber.nthUglyNumber(100));
    wholeStopWatch.stop();
    System.out.println(wholeStopWatch.elapsed(TimeUnit.MICROSECONDS));
  }
}
